//
// Created by mac on 2/22/22.
//

#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    if(nums.size()==0){return -1;}
    int left = 0;
    int right = nums.size()-1;

    while (left<=right){
        int mid = left + (right-left);
        if(target==nums[mid]){return mid;}

        if(nums[left]<=nums[mid]){//左边有序
            if(target>=nums[left] && target<nums[mid]){
                right = mid-1;
            } else{
                left = mid+1;
            }
        }else{
            //右边有序
            if(target>nums[mid] && target<=nums[right]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
    }
    return -1;
}